/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */

// 第一种找不到key

var deleteNode = function (root, key) {
    if (!root) return null

    function recursion(root, key) {
        if (!root) return
        if (root.val !== key) {
            if (root.val < key) {
                root.right && (root.right = recursion(root.right, key))
            } else {
                root.left && (root.left = recursion(root.left, key))
            }

            return root

        }

        // 这里就是排除了第一种情况, 已经找到了删除的结节,
        if (root.val !== key) return

        // 第二种情况
        // 删除的节点没有左边节点,
        if (!root.left && root.right) {
            root = root.right
        } else if (!root.right && root.left) {
            // 第三种情况
            // 删除的节点没有右边节点,
            root = root.left
        } else if (!root.right && !root.left) {
            // 第四中情况
            // 左右都没有节点
            root = null
        } else if (root.right && root.left) {
            // 第五种情况
            // 俩边都有子节点,
            // 可以选择把当前节点的右边全部给挪到左边的最右侧字节点
            let left = root.left
            let right = root.right
            root = left
            let cur = root
            while (cur.right) {
                cur = cur.right
            }
            cur.right = right
        }

        return root;


    }
    root = recursion(root, key)
    return root
};